package com.hyc.DataStructure.LinkedList;

import java.util.Stack;

/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.LinkedList
 * @className: LinkedlistDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2021/12/17 16:24
 * @version: 1.0
 */
public class LinkedlistDemo {
    public static void main(String[] args) {
        // 设置一些英雄对象
        HeroNode heroNode = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode1 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode2 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode3 = new HeroNode(4, "林冲", "豹子头");
        HeroNode heroNode4 = new HeroNode(5, "宋江", "及时雨");
        HeroNode heroNode5 = new HeroNode(6, "卢俊义", "玉麒麟");
        HeroNode heroNode6 = new HeroNode(7, "吴用", "智多星");
        HeroNode heroNode7 = new HeroNode(8, "林冲", "豹子头");
        // 声明单向链表
        SingleLinkedlist linkedlist = new SingleLinkedlist();
        SingleLinkedlist linkedlist1 = new SingleLinkedlist();
        //加入我们的英雄节点
        //linkedlist.add(heroNode);
        //linkedlist.add(heroNode1);
        //linkedlist.add(heroNode2);
        //linkedlist.add(heroNode3);
        //加入按照编号
        linkedlist.addByOrder(heroNode);
        linkedlist.addByOrder(heroNode3);
        linkedlist.addByOrder(heroNode2);
        linkedlist.addByOrder(heroNode1);
        //加入第二个链表
        linkedlist1.addByOrder(heroNode4);
        linkedlist1.addByOrder(heroNode5);
        linkedlist1.addByOrder(heroNode6);
        linkedlist1.addByOrder(heroNode7);
        //合并两个链表并且保证有序
        System.out.println("输出合并之后的链表");
        SingleLinkedlist.mergeList(linkedlist1.getHead(), linkedlist.getHead());
        linkedlist.List();
        //输出有效的节点数量
        System.out.println("输出链表的有效节点数量");
        System.out.println(SingleLinkedlist.getlength(linkedlist.getHead()));
        //找到了 k节点
        System.out.println("输出index的链表");
        System.out.println(SingleLinkedlist.getLastIndexNode(linkedlist.getHead(), 2));
        //反向输出链表 不破坏结构的
        System.out.println("不改变结构输出反向链表");
        SingleLinkedlist.showreverseList(linkedlist.getHead());
        //输出反转链表
        System.out.println("输出反转链表");
        SingleLinkedlist.reverseList(linkedlist.getHead());
        linkedlist.List();
        System.out.println("输出列表");
        //输出节点信息
        linkedlist.List();
        System.out.println("更新数据后");
        linkedlist.updateNode(new HeroNode(1, "冷环渊", "编码大师"));
        //输出节点信息
        linkedlist.List();
        System.out.println("删除数据后输出");
        linkedlist.DeleteNode(1);
        linkedlist.List();
    }
}

class SingleLinkedlist {
    //创建一个头结点
    HeroNode head = new HeroNode(0, "", "");

    public HeroNode getHead() {
        return head;
    }

    public void setHead(HeroNode head) {
        this.head = head;
    }

    //加入链表
    public void add(HeroNode node) {
        //头节点不能动 这里我们用一个临时指针来记录
        HeroNode temp = head;
        //遍历链表
        while (true) {
            //遍历为空就代表找了最后一个节点
            //不为空就后移一位继续找
            if (temp.next == null) {
                break;
            }
            //没有找到最后就后移 temp
            temp = temp.next;
        }
        //跳出while证明找到了最后的节点，将我们的新节点加入到最后的节点的next即可
        temp.next = node;
    }

    //添加节点 第二种方法
    public void addByOrder(HeroNode node) {
        /*
         * 因为头结点不能动，我们通过指针来记录头节点来帮助找到添加的位置
         *因为是单链表我们找的是 Temp是位于添加位置的前一个节点，否则插入不了
         * */
        //创建一个临时变量
        HeroNode temp = head;
        //用来标识 英雄是否存在 默认为不存在（false）
        boolean flag = false;
        while (true) {
            //找到最后为空的位置
            if (temp.next == null) {
                break;
            }
            //如果temp的下一个no 大于 我们加入的节点，就往temp加入
            if (temp.next.No > node.No) {
                break;
            }
            //如果下一个节点等于 加入节点的No 那么就代表已经存在了节点
            else if (temp.next.No == node.No) {
                //将flag 修改为 true 代表已经存在
                flag = true;
                break;
            }
            //如果上面的都没达成就代表当前节点位置不对，向后继续遍历
            temp = temp.next;
        }
        //    判断 flag的值
        if (flag) {
            //如果为 true 代表节点已经存在
            System.out.printf("当前节点%d已经存在了，不能加入\n", node.No);
        } else {
            //    如果为false 那代表符合插入条件并且不存在与当前链表
            node.next = temp.next;
            temp.next = node;
        }

    }

    //修改节点信息
    public void updateNode(HeroNode newHeroNode) {
        if (head.next == null) {
            System.out.println("链表是空的");
        }
        //这里是头节点不能修改，我用 temp 来指向头结点
        HeroNode temp = head.next;
        // 是否找到了no的标识
        boolean flag = false;
        while (true) {
            //找到最后一个
            if (temp == null) {
                break;
            }
            if (temp.No == newHeroNode.No) {
                //如果等于 那么代表可以修改
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            //  true 修改信息
            temp.NickName = newHeroNode.NickName;
            temp.Name = newHeroNode.Name;
        } else {
            System.out.printf("没有找到 %d 这个节点", newHeroNode.No);
        }
    }

    //删除节点信息
    public void DeleteNode(int no) {
        HeroNode temp = head;
        // 用来标注 是不是可以删除
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.No == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag 删除Node
        if (flag) {
            //找到的话就删除，这里我们只需要指向空 GC会回收
            temp.next = temp.next.next;
        } else {
            System.out.printf("要删除的 %d 没有找到", no);
        }
    }

    //遍历链表
    public void List() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //头节点不能动 这里我们用一个临时指针来记录
        HeroNode temp = head.next;
        while (true) {
            //遍历为空就代表找了最后一个节点
            if (temp == null) {
                break;
            }
            //输出节点
            System.out.println(temp);
            //后移一位
            temp = temp.next;
        }
    }

    /**
     * @author 冷环渊 Doomwatcher
     * @context: 方法 找到链表的有效节点的个数（有头节点的要忽略头节点）
     * @date: 2021/12/18 13:14
     * @param heroNode
     * @return: int
     */
    public static int getlength(HeroNode heroNode) {
        if (heroNode.next == null) {
            return 0;
        }
        int length = 0;
        HeroNode cur = heroNode.next;
        while (cur != null) {
            length++;
            //后移遍历
            cur = cur.next;
        }
        return length;
    }

    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 新浪链表面试题 查找链表中的第k个节点
     * 思路：
     * 1.编写一个方法，接收head 节点，同时接收一个index
     * 2，index表示的是倒数第index 个节点
     * 3. 先把链表从头到尾遍历 得到链表的总长度 getlength
     * 4。得到Size之后 我们从链表的第一个开始遍历（Size-index）个，就可以得到
     * 5. 如果找到了 则返回该节点否则返回null
     * @date: 2021/12/18 15:12
     * @param head
     * @param index
     * @return: com.hyc.DataStructure.LinkedList.HeroNode
     */
    public static HeroNode getLastIndexNode(HeroNode head, int index) {
        // 如果除去头节点之后没有新的节点就代表链表是空的，返回空对象
        if (head.next == null) {
            return null;
        }
        // 获取到链表的长度
        int Size = SingleLinkedlist.getlength(head);
        //声明一个零时变量指向第一个有效的节点
        HeroNode cur = head.next;
        //假设 我们的例子是一共有三个有效节点 3 这里我们index 为 2 那么3-2 = 1 找到了倒数第二个的节点
        for (int i = 0; i < Size - index; i++) {
            cur = cur.next;
        }
        //找到节点之后我们直接返回即可
        return cur;
    }

    /**
     * @author 冷环渊 Doomwatcher
     * @context: 腾讯面试题 反转链表
     * 思路:
     * 1.先定义一个节点 reverseHead = new HeroNode();
     * 2.从头遍历原来的链表，每次遍历一个节点就将其取出并且放到信的链表的最前端，
     * 3.原来的链表head.next = reverseHead.Next
     * @date: 2021/12/18 15:38
     * @param head
     * @return: void
     */
    public static void reverseList(HeroNode head) {
        if (head.next == null || head.next.next == null) {
            return;
        }
        //需要新的一个空的头
        HeroNode reverseHead = new HeroNode(0, "", "");
        // 获得第一个有效的节点
        HeroNode cur = head.next;
        //指向[cur]的下一个的节点
        HeroNode next = null;
        while (cur != null) {
            //保存当前的节点的下一个位置 有用
            next = cur.next;
            // 将cur的下一个指向 新的链表的最前端
            cur.next = reverseHead.next;
            //将新链表的最前端为cur
            reverseHead.next = cur;
            //cur 继续向后遍历
            cur = next;
        }
        head.next = reverseHead.next;
    }

    /**
     * @author 冷环渊 Doomwatcher
     * @context: 百度面试题， 在不破坏链表结构的情况下 反向输出链表
     * 这里我们利用 一个 即将学到的 数据结构叫 栈
     * 栈结构的特点就是 先进后出
     * 将链表的节点按顺序遍历压入栈
     * 利用栈先进后出的特质，就可以保证性能的情况下输出不改变结构的倒序链表
     * @date: 2021/12/19 13:48
     * @param
     * @return: void
     */
    public static void showreverseList(HeroNode node) {
        if (node.next == null) {
            return;
        }
        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = node.next;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }

    /**
     * @author 冷环渊 Doomwatcher
     * @context: 合并两个链表 并且有序
     * @date: 2021/12/19 14:15
     * @param list1
     * @param list2
     * @return: com.hyc.DataStructure.LinkedList.SingleLinkedlist
     */
    public static HeroNode mergeList(HeroNode list1, HeroNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        HeroNode head = new HeroNode(0, "", "");
        HeroNode temp = head;
        while (list1 != null && list2 != null) {
            if (list1.No < list2.No) {
                temp.next = list1;
                list1 = list1.next;
            } else {
                temp.next = list2;
                list2 = list2.next;
            }
            temp = temp.next;
        }
        if (list1 == null) {
            temp.next = list2;
        }
        if (list2 == null) {
            temp.next = list1;
        }
        return head.next;
    }
}


/**
 * 编写 水浒传英雄 节点
 *  用于存放每个英雄的属性
 * */
class HeroNode {
    //排名
    public int No;
    // 姓名
    public String Name;
    //昵称
    public String NickName;
    // 下一个是哪位好汉
    public HeroNode next;

    public HeroNode(int hNo, String hName, String hNickName) {
        this.No = hNo;
        this.Name = hName;
        this.NickName = hNickName;
    }

    //方便输出语句输出
    @Override
    public String toString() {
        return "HeroNode{" +
                "No=" + No +
                ", Name='" + Name + '\'' +
                ", NickName='" + NickName + '\'' +
                '}';
    }
}